#include <stdio.h>
#include <stdlib.h>

typedef int ElemSet; /* 默认元素为整数*/
typedef struct RecordNode *Records;
struct RecordNode {
    ElemSet key; /* 关键字 */
    /* 其他属性由用户自定义 */
};

typedef Records TElemSet;
typedef struct AVLTreeNode *Position; /* 树结点指针是元素的位置 */
typedef struct AVLTreeNode *AVLTree;
struct AVLTreeNode {
    TElemSet data; /* 数据元素 */
    int height; /* 结点高度 */
    AVLTree left; /* 左孩子指针 */
    AVLTree right; /* 右孩子指针 */
};
#define NIL NULL

int GetHeight(AVLTree tree) {
    if (tree == NIL) {
        return 0;
    } else {
        return tree->height;
    }
}

int Max(int x, int y) {
    return (x > y) ? x : y;
}

/* 算法11-8：AVL树的左单旋转（RR型） RRSingleRotation(root) */
AVLTree RRSingleRotation(AVLTree root) {
    AVLTree new_root;

    new_root = root->right;
    root->right = new_root->left;
    new_root->left = root;
    root->height = Max(GetHeight(root->left), GetHeight(root->right)) + 1;
    new_root->height = Max(GetHeight(new_root->left),
                           GetHeight(new_root->right)) + 1;
    return new_root;
}
/* 算法11-8 结束 */

AVLTree LLSingleRotation(AVLTree root) {
    AVLTree new_root;

    new_root = root->left;
    root->left = new_root->right;
    new_root->right = root;
    root->height = Max(GetHeight(root->left), GetHeight(root->right)) + 1;
    new_root->height = Max(GetHeight(new_root->left),
                           GetHeight(new_root->right)) + 1;
    return new_root;
}

/* 算法11-9：AVL树的先左后右双向旋转 (LR型） LRDoubleRotation(root) */
AVLTree LRDoubleRotation(AVLTree root) {
    AVLTree middle, new_root;

    middle = root->left;
    new_root = middle->right;
    middle->right = new_root->left;
    new_root->left = middle;
    root->left = new_root->right;
    new_root->right = root;
    middle->height = Max(GetHeight(middle->left), GetHeight(middle->right)) + 1;
    root->height = Max(GetHeight(root->left), GetHeight(root->right)) + 1;
    new_root->height = Max(middle->height, root->height) + 1;
    return new_root;
}
/* 算法11-9 结束 */

AVLTree RLDoubleRotation(AVLTree root) {
    AVLTree middle, new_root;

    middle = root->right;
    new_root = middle->left;
    middle->left = new_root->right;
    new_root->right = middle;
    root->right = new_root->left;
    new_root->left = root;
    middle->height = Max(GetHeight(middle->left), GetHeight(middle->right)) + 1;
    root->height = Max(GetHeight(root->left), GetHeight(root->right)) + 1;
    new_root->height = Max(middle->height, root->height) + 1;
    return new_root;
}

/* 算法11-7 AVL树的插入 InsertAVL(tree, x) */
AVLTree InsertAVL(AVLTree tree, TElemSet x) {
    if (tree == NIL) { /* 若是空树，为x创建新的树根结点 */
        tree = (AVLTree)malloc(sizeof(struct AVLTreeNode));
        tree->data = x;
        tree->height = 1;
        tree->left = tree->right = NIL;
    } else { /* 若不是空树 */
        if (x->key < tree->data->key) {
            tree->left = InsertAVL(tree->left, x);
            if (GetHeight(tree->left) - GetHeight(tree->right) >
                    1) { /* 左子树变高失衡 */
                if (x->key < tree->left->data->key) { /* 右单旋转 (LL型) */
                    tree = LLSingleRotation(tree);
                } else { /* 先左后右双向旋转 (LR型) */
                    tree = LRDoubleRotation(tree);
                }
            }
        } else if (x->key > tree->data->key) {
            tree->right = InsertAVL(tree->right, x);
            if (GetHeight(tree->left) - GetHeight(tree->right) <
                    -1) { /* 右子树变高失衡 */
                if (x->key > tree->right->data->key) { /* 左单旋转（RR型） */
                    tree = RRSingleRotation(tree);
                } else { /* 先先右后左双向旋转（RL型） */
                    tree = RLDoubleRotation(tree);
                }
            }
        } /* x.key = bstree.data.key 时不重复插入 */
    }
    tree->height = Max(GetHeight(tree->left), GetHeight(tree->right)) + 1;
    return tree;
}
/* 算法11-7 结束 */

void Visit(AVLTree tree) {
    printf("%d\n", tree->data->key);
}

void PreOrder(AVLTree tree) {
    if (tree != NULL) {
        Visit(tree);
        PreOrder(tree->left);
        PreOrder(tree->right);
    }
}

int main(void) {
    TElemSet x;
    AVLTree tree;
    int n, i;

    tree = NIL;
    scanf("%d", &n);
    for (i = 0; i < n; i++) {
        x = (TElemSet)malloc(sizeof(struct RecordNode));
        scanf("%d", &x->key);
        tree = InsertAVL(tree, x);
    }
    PreOrder(tree);

    return 0;
}